
/*
 * @lc app=leetcode.cn id=141 lang=javascript
 *
 * [141] 环形链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
// JSON.stringify报错就是有环
// var hasCycle = function(head) {
//   try {
//     JSON.stringify(head)
//   } catch (e) {
//     return true
//   }
//   return false
// };

// // 给遍历过的节点打记号，如果遍历过程中遇到有记号的说明已环
// var hasCycle = function(head) {
//   while (head) {
//     if (head.tag) {
//       return true
//     }
//     head.tag = true
//     head = head.next
//   }
//   return false
// };

// // 题目说了范围不超过100000，没超过size能发现空节点就是没有环， 超过了就是有环
// var hasCycle = function(head) {
//   let i = 0, size = 100000
//   let node = head
//   while (++i <= size) {
//     if (!node) return false
//     node = node.next
//   }
//   return true
// };

// 快慢指针
var hasCycle = function(head) {
  if (head === null || head.next === null) return false
  let slow = head
  let fast = head.next
  while (slow !== fast) {
    if (fast === null || fast.next === null) {
      return false
    }
    slow = slow.next
    // 每次循环多跑一点，如果fast和slow相等说明闭环了
    fast = fast.next.next
  }
  return true
};

// @lc code=end

